#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> ans;
        if(array.empty()) return ans;
        vector<int> mx = {1,0,-1,0};
        vector<int> my = {0,1,0,-1};

        int m = array.size();
        int n = array[0].size();

        
        int mn = m*n;
        int x=0; int y=0; int cnt=0;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for(int idx=0; idx<mn; ++idx){
            ans.push_back(array[y][x]);
            vis[y][x] = true;
            for(int i=0; i<4; ++i){
                int newx = x+mx[cnt%4];
                int newy = y+my[cnt%4];
                if(-1<newx && newx<n && -1<newy && newy<m && !vis[newy][newx]){
                    x = newx;
                    y = newy;
                    break;
                }
                ++cnt;
            }
        }
        return ans;
    }
};

// //solution 2
// class Solution {
// public:
//     vector<int> spiralArray(vector<vector<int>>& array) {
//         if(array.size() == 0 || array[0].size() == 0)
//         {
//             return {};
//         }

//         vector<int> res;

//         int l = 0, r = array[0].size() - 1;
//         int u = 0, d = array.size() - 1;

        


//         while(l <= r && u <= d)
//         {
//             for(int i = l; i <= r; i++)
//             {
//                 res.push_back(array[u][i]);
//             }

//             for(int i = u + 1; i <= d; i++)
//             {
//                 res.push_back(array[i][r]);
//             }
//             if(l < r && u < d)
//             {
//                 for(int i = r - 1; i > l; i--)
//                 {
//                     res.push_back(array[d][i]);
//                 }

//                 for(int i = d; i > u; i--)
//                 {
//                     res.push_back(array[i][l]);
//                 }
//             }
//             l++;
//             r--;
//             u++;
//             d--;
//         }
//         return res;
//     }
    
// };

int main(){
    Solution solution;
    vector<vector<int>> array = {{1, 2}};
    solution.spiralArray(array);
}